package lc.q1_50;

import java.util.Random;

/**
 * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 *
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * 必须原地修改，只允许使用额外常数空间。
 *
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 *
 */
public class Q31 {
    public void nextPermutation(int[] nums) {
        // 思路： 比较相邻的
        int i;
        for (i = nums.length - 1; i >= 1; i--) {
            int num1 = nums[i];
            int num2 = nums[i-1];
            if (num1 > num2) {
                // 寻找后面比num2大的最小值
                int j = i;
                int change = i;
                for (; j < nums.length; j++) {
                    if (nums[j] > num2 && nums[j] < num1) {
                        num1 = nums[j];
                        change = j;
                    }
                }
                nums[i-1] = num1;
                nums[change] = num2;
                break;
            }
        }
        // 调换完之后，应该对调换后的数组按字典序最小排序
        resort(nums, i);
    }

    public void resort(int[] nums, int start) {
        // 只能从start开始排
        // 由于不能有额外空间，这里可选取的排序算法只有一部分
        for (int i = nums.length - 1; i >= start ; i--) {
            for (int j = start; j < i; j++) {
                // 比较j j+1
                if (nums[j] > nums[j+1]) {
                    // 调换
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        final Random random = new Random();
        final int length = random.nextInt(40)+10;
        System.out.println(length);
        int[] nums = new int[length];
        for (int i = 0; i < length; i++) {
            nums[i] = random.nextInt(30);
        }
        for (int num : nums) {
            System.out.print(num+"\t");
        }
        System.out.println();
        final Q31 q31 = new Q31();
        q31.nextPermutation(nums);
        for (int num : nums) {
            System.out.print(num+"\t");
        }
        System.out.println();
    }

}
